'''
仅用队列结构实现栈结构, Queue 是一个单端队列
'''
from queue import Queue
class two_queues_stack:
    def __init__(self) -> None:
        self._queue = Queue()
        self._help = Queue()
    def push(self, obj: object):
        self._queue.put(obj)
    def peek(self) -> object:  #永远是从queue返回
        if self._queue.empty() :
            raise Exception('Stack is empty!')
        while self._queue.qsize() != 1:
            self._help.put(self._queue.get())
        res = self._queue.get()
        self._help.put(res)
        self._help, self._queue = self._queue, self._help
        return res
    def pop(self) -> object:
        if self._queue.empty() :
            raise Exception('Stack is empty!')
        while self._queue.qsize() != 1:
            self._help.put(self._queue.get())
        res = self._queue.get()               
        self._help, self._queue = self._queue, self._help
        return res

#225. 用队列实现栈
from queue import Queue
class MyStack:
    def __init__(self):
        self._stack = Queue()
        self._help = Queue()

    def push(self, x: int) -> None:
        self._stack.put(x)

    def pop(self) -> int:
        while self._stack.qsize() > 1:
            self._help.put(self._stack.get())
        tmp = self._stack.get()
        self._stack, self._help = self._help, self._stack
        return tmp

    def top(self) -> int:
        while self._stack.qsize() > 1:
            self._help.put(self._stack.get())
        tmp = self._stack.get()
        self._help.put(tmp)
        self._stack, self._help = self._help, self._stack
        return tmp
    def empty(self) -> bool:
        if self._stack.empty() and self._help.empty():
            return True
        return False


'''
仅用栈结构实现队列结构
你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
'''
# 面试题 03.04. 化栈为队
from collections import deque
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self._push = deque()
        self._pop = deque()


    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self._push.append(x)


    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self._pop) == 0:
            while len(self._push) != 0:
                self._pop.append(self._push.pop())
        return self._pop.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self._pop) == 0:
            while len(self._push) != 0:
                self._pop.append(self._push.pop())
        tmp = self._pop.pop()
        self._pop.append(tmp)
        return tmp

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        if len(self._pop) == 0 and len(self._push) == 0:
            return True
        return False



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

'''
Python 标准库中的 LifoQueue 堆栈实现是同步的，并提供锁定语义以支持多个并发生产者和消费者。

锁定语义可能会有所帮助，或者它们可能只会产生不必要的开销。 在这种情况下，最好使用列表或双端队列作为通用堆栈：
'''
from queue import LifoQueue

class two_stacks_queue:
    def __init__(self) -> None:
        self._push = LifoQueue()
        self._pop = LifoQueue()
    def push(self, obj: object):
        self._push.put(obj)
    def poll(self) -> object:
        if  self._push.empty() and self._pop.empty():
            raise Exception('queue is empty!')
        elif self._pop.empty():
            while not self._push.empty():  #开始倒数据，全部倒完
                self._pop.put(self._push.get())
        return self._pop.get()
    def peek(self) -> object:
        if  self._push.empty() and self._pop.empty():
            raise Exception('queue is empty!')
        elif self._pop.empty():
            while not self._push.empty():  #开始倒数据，全部倒完
                self._pop.put(self._push.get())
        tmp = self._pop.get()
        self._pop.put(tmp)
        return tmp



a = two_queues_stack()
a.push(1)
a.push(2)
a.push(3)
a.peek()
a.pop()
a.peek()
a.pop()
a.peek()
a.pop()
a.peek()
a.pop()

b = two_stacks_queue()
b.push(1)
b.push(2)
b.push(3)
b.peek()
b.pop()
b.peek()
b.pop()
b.peek()
b.pop()
b.peek()
b.pop()